package com.atguigu.sort;

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Arrays;
import java.util.Random;

/**
 * @Author : SunFeng
 * @Description: 冒泡排序算法
 * @Date : 2021/6/30  14:33
 */
public class BubbleSort {

    public static void main(String[] args) {
        //int[] array = {10, 3, -1, 9, -2};
        int[] array = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array[i] = (int) (Math.random() * 8000);
        }
       // System.out.println(Arrays.toString(array));
        System.out.println(LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));
        bubbleSort(array);
        System.out.println(LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));
       // System.out.println(Arrays.toString(array));
    }

    /**
     * 第一，冒泡排序是原地排序算法吗？
     * 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
     * 第二，冒泡排序是稳定的排序算法吗？
     * 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，
     * 相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
     * 第三，冒泡排序的时间复杂度是多少？
     * 最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，
     * 要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。
     *
     * @param array
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {

            boolean flag = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                int temp = 0;
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true; // 表示有数据交换
                }
            }
            if (!flag) break; // 没有数据交换，提前退出
           // System.out.println(Arrays.toString(array));
        }
    }

}
